import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-11-19
 * Time: 18:23
 */
public class Coin {
    public static  int minNum(int money,int[][]moneycount){
        //按照生活常识，我们需要尽可能的用最大的面值，最少的张数来达到至少需要的钱数，这样才符合题目的要求
        int num=0;//记录每个面值至少需要的张数
        int cnt=0;//记录总共至少需要多少张
        for(int i=moneycount.length-1;i>=0;i--){
            num=Math.min(money/moneycount[i][0],moneycount[i][1]);//用每次剩下的钱去除以当前的面值就是每个面值需要的张数，让后再让他跟当前面值有多少张的张数去取最小值
            money=money-num*moneycount[i][0];//找钱之后剩下有多少钱
            cnt+=num;//用了多少好张
        }
        if(money>0){
            return -1;//如果减去之后剩下的钱还是大于0，那么就不够
        }else{
            return cnt;//够了，返回张数
        }

    }

    public static void main(String[] args) {
        int[][] moneyconnt={{1,3},{2,4},{5,6},{10,2},{20,10},{50,3},{100,1}};
        System.out.println("请输入你要支付的钱：");
        Scanner scan=new Scanner(System.in);
        int money=scan.nextInt();
        int ret=minNum(money,moneyconnt);
        System.out.println("支付"+money+"元"+"至少需要"+ret+"张钱币");
    }
}
